//题目:
// 在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。
// 你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。
// 给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
// 如输入这样的一个二维数组，
// [
//     [1,3,1],
//     [1,5,1],
//     [4,2,1]
// ]
// 那么路径 1→3→5→2→1 可以拿到最多价值的礼物，价值为12
#include<iostream>
#include<limits.h>
#include<vector>
#include<map>

using namespace std;
//代码
class Solution 
{
    int ret=INT_MIN;
    int dx[2]={0,1},dy[2]={1,0};
    map<pair<int,int>,int> dp;//记录(i,j)位置到终点的路径最大值
public:
    //全排列
    // void dfs(const vector<vector<int> >& grid,int row,int col,int sum_value)
    // {
    //     //进入该函数时，grid[row][col]已经被加到sum_value中了
    //     if(row==grid.size()-1 && col==grid[0].size()-1){
    //         ret=max(ret,sum_value);
    //         return;
    //     }
    //     //寻找下一个落脚点
    //     for(int i=0;i<2;i++)
    //     {
    //         int x=row+dx[i],y=col+dy[i];
    //         if(x>=0 && x<grid.size() && y>=0 && y<grid[0].size())
    //             dfs(grid,x,y,sum_value+grid[x][y]);
    //     }
    // }

    //记忆化搜索
    int dfs(const vector<vector<int> >& grid,int row,int col)
    {
        //进入该函数时，grid[row][col]已经被加到sum_value中了
        if(row==grid.size()-1 && col==grid[0].size()-1) return grid[row][col];

        if(dp.count({row,col})) return dp[{row,col}];

        int max_sum=INT_MIN;//记录(row,col)到终点位置的路径最大值
        //寻找下一个落脚点
        for(int i=0;i<2;i++)
        {
            int x=row+dx[i],y=col+dy[i];
            if(x>=0 && x<grid.size() && y>=0 && y<grid[0].size())
                max_sum=max(max_sum,grid[row][col]+dfs(grid,x,y));
        }

        dp[{row,col}]=max_sum;
        return max_sum;
    }
    int maxValue(vector<vector<int> >& grid) 
    {
        // write code here
        //法一：全排列————超时
        // dfs(grid,0,0,grid[0][0]);
        // return ret;

        //法二：优化————记忆化搜索
        // return dfs(grid,0,0);

        //法三：动态规划
        //1.创建dp表————记录(0,0)位置到(i,j)位置的路径最大值
        map<pair<int,int>,int> dp;
        //2.初始化
        for(int i=0;i<grid.size();i++)
        {
            if(i==0)dp[{i,0}]=grid[i][0];
            else dp[{i,0}]=dp[{i-1,0}]+grid[i][0];
        }
        for(int j=0;j<grid[0].size();j++)
        {
            if(j==0)dp[{0,j}]=grid[0][j];
            else dp[{0,j}]=dp[{0,j-1}]+grid[0][j];
        }
        //3.填表————动态转移方程：dp[{i,j}]=grid[i][j]+max(dp[{i-1,j}],dp[{i,j-1}])
        for(int i=1;i<grid.size();i++)
        {
            for(int j=1;j<grid[0].size();j++)
            {
                dp[{i,j}]=grid[i][j]+max(dp[{i-1,j}],dp[{i,j-1}]);
            }
        }
        //4.确定返回值
        return dp[{grid.size()-1,grid[0].size()-1}];
    }
};